package mazeAssignment;

import java.util.Arrays;

/**
 * A basic implementation of a binary-search-tree.
 * Not automatically balanced. Works reasonably well with more or less random input.
 * @author Marcel Hekman
 */
public class BinaryTree<AnyType extends Comparable<? super AnyType>> {
	
	private BinaryNode<AnyType> root;
	
	
	public BinaryTree()
	{
		this.root = null;
	}
	
	public BinaryTree(BinaryNode<AnyType> r)
	{
		this.root = r;
	}
	
	public BinaryTree(AnyType[] arr)
	{
		Arrays.sort( arr );
		this.root = arrayPartToNode(arr, 0, arr.length);
	}
	
	
	//Used for array import
	private BinaryNode<AnyType> arrayPartToNode(AnyType[] arr, int start, int end)
	{
		int nodes = end - start;
		
		if(nodes == 2)
		{
			BinaryNode<AnyType> left = new BinaryNode<AnyType>(arr[start]);
			return new BinaryNode<AnyType>(arr[start+1], left, null);
		}
		else if(nodes == 3)
		{
			BinaryNode<AnyType> left = new BinaryNode<AnyType>(arr[start]);
			BinaryNode<AnyType> right = new BinaryNode<AnyType>(arr[start+2]);
			return new BinaryNode<AnyType>(arr[start+1], left, right);
		}
		else
		{
			int half = (nodes / 2);
			BinaryNode<AnyType> left = arrayPartToNode(arr, start, start+half);
			BinaryNode<AnyType> right = arrayPartToNode(arr, start+half+1, end);
			return new BinaryNode<AnyType>(arr[start+half], left, right);
		}
	}
	
	
	
	
	public void add(AnyType item)
	{
		if(this.root == null)
		{
			this.root = new BinaryNode<AnyType>(item);
		}
		else
		{
			this.root.add(item);
		}
		
	}
	
	public boolean contains(AnyType item)
	{
		if(this.root == null)
			return false;
		
		
		BinaryNode<AnyType> current = this.root;
		
		while(current != null)
		{
			int compValue = item.compareTo(current.element);
			
			if(compValue < 0)
				current = current.left;
			else if(compValue > 0)
				current = current.right;
			else
				return true;
		}
		
		return false;
	}
	
	public void removeKth(int index)
	{
		if(this.root != null)
		{
			AnyType item = (this.root.findKth(index+1)).element;
			this.remove( item );
		}
	}
	
	public void remove(AnyType item)
	{
		if(this.root != null)
		{
			this.root = this.root.remove(item);
		}
	}
	
	public AnyType get(int index)
	{
		if(this.root != null)
		{
			return (this.root.findKth(index+1)).element;
		}
		
		return null;
	}
	
	public int size()
	{
		if(this.root != null)
			return this.root.size();
		
		return 0;
	}
	
	public BinaryNode<AnyType> getRoot()
	{
		return this.root;
	}
	
	public void printInOrder()
	{
		if(this.root != null)
		{
			this.root.printInOrder();
		}
	}
	
	public int height()
	{
		if(this.root != null)
		{
			return this.root.height();
		}
		
		return 0;
	}
	
	public boolean isEmpty()
	{
		return this.root == null;
	}
}
